import static java.io.ObjectInputFilter.merge;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 张宇田
 * Date: 2025-03-13
 * Time: 17:22
 */
//x写一个sort类，然后里面写方法
public class Sort {



    public static void insertSort(int[] arr){
        for (int i = 1 ; i<arr.length ; i++){
            int tmp = arr[i];
            int j = i-1;
            for(;j>=0;j--){
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }//确实放到循环外边就可以了，每一次循环就有一个要放前面啊的tmp
            arr[j+1] = tmp;

        }
    }

    //快速排序
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }

    private static void quick(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        int pivot = partition(arr,left,right);
        quick(arr,left ,pivot -1 );
        quick(arr,pivot+1,right);

    }
    private static int partition(int[]arr,int start,int end){
        //保留初始下标，否则后面没得换
        int index = start;

        int piv = arr[start];
        while (start<end){
            //必须要先是end--
            while(start<end &&arr[end]>=piv){
                end--;
            }
            while(start<end && arr[start]<=piv){
                start++;
            }

            swap(arr,start,end);
        }
        swap(arr,index,start);
        return start;
    }
    private static void swap(int[] arr,int x,int y){
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }

    //归并排序
    public static void mergeSort(int[] arr){
        int left = 0;
        int right = arr.length;
        merge(left,right,arr);

    }
    private static void merge(int left , int right , int[] arr){


        int mid = (right+left)/2;
        //将数组划分
        merge(left,mid,arr);
        merge(mid+1,right,arr);

        //




    }
}

